package leetcode_周赛._2023._03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yezh
 * @date 2023/3/26 13:40
 * 338 场周赛
 * AC_2
 */
public class _26 {

    /**
     * 使数组元素全部相等的最少操作次数
     * 算法: 前缀和 + 二分查找
     */
    public List<Long> minOperations(int[] nums, int[] queries) {
        int n = nums.length;
        Arrays.sort(nums);
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        List<Long> ans = new ArrayList<>(queries.length);
        for (int query : queries) {
            // 找打第一次大于 query 的数的位置, 则小于 query 的数有 t 个
            int t = binarySearch(nums, query + 1);
            long left = (long) query * t - prefix[t];
            long right = prefix[n] - prefix[t] - (long) query * (n - t);
            ans.add(left + right);
        }
        return ans;
    }

    int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int mid;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

}
